0290. 单词规律【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法

1. 📝 题目描述

• leetcode

给定一种规律 pattern 和一个字符串 s，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例 1：

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2：

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3：

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

---

提示：

• 1 <= pattern.length <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和 ' '
• s 不包含 任何前导或尾随对空格
• s 中每个单词都被 单个空格 分隔

2. 🎯 s.1 - 暴力解法

js

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function (pattern, s) {
  // 将字符串 s 按空格分割成单词数组
  const words = s.split(' ')

  // 如果 pattern 的长度与单词数量不一致，直接返回 false
  if (pattern.length !== words.length) return false

  // 建立双向映射关系
  const charToWord = new Map() // 字符到单词的映射
  const wordToChar = new Map() // 单词到字符的映射

  // 遍历 pattern 和 words，建立映射关系
  for (let i = 0; i < pattern.length; i++) {
    const char = pattern[i]
    const word = words[i]

    // 检查字符到单词的映射
    if (charToWord.has(char)) {
      // 如果字符已有映射但与当前单词不一致，返回 false
      if (charToWord.get(char) !== word) {
        return false
      }
    } else {
      // 建立新的映射
      charToWord.set(char, word)
    }

    // 检查单词到字符的映射
    if (wordToChar.has(word)) {
      // 如果单词已有映射但与当前字符不一致，返回 false
      if (wordToChar.get(word) !== char) {
        return false
      }
    } else {
      // 建立新的映射
      wordToChar.set(word, char)
    }
  }

  return true
}

• 时间复杂度：$O(n)$，其中 $n$ 是 pattern 的长度，需要遍历一次
• 空间复杂度：$O(n)$，需要存储映射关系和分割后的单词数组
• 相似：
  • 205. 同构字符串
• 题解执行流程：
  • 预处理：
    • 将字符串 s 按空格分割成单词数组
    • 检查 pattern 长度与单词数量是否一致
  • 建立双向映射：
    • 使用两个 Map 分别记录字符到单词和单词到字符的映射
    • 确保映射关系是一一对应的
  • 验证映射：
    • 遍历 pattern 和单词数组
    • 检查是否存在冲突的映射关系
  • 返回结果：
    • 如果所有映射关系都一致，返回 true
    • 否则返回 false